package me.chan.functional;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class FunctionalDemo {

	public static void main(String[] args) {
		//find all the subsets of the given set {1,4,9}, included the empty set.
		List<Integer> list = Arrays.asList(1,4,9,16);
		List<List<Integer>> subsetList = getSubsets(list);
		subsetList.stream().forEachOrdered(l -> System.out.println(l));
		System.out.println(subsetList.stream().count());
	}

	static List<List<Integer>> getSubsets(List<Integer> list) {
		if (list.isEmpty()) {
			List<List<Integer>> answer = new ArrayList<>();
			answer.add(Collections.emptyList());
			return answer;
		}
		Integer first = list.get(0);
		List<Integer> rest = list.subList(1, list.size());
		List<List<Integer>> subanswer1 = getSubsets(rest);
		List<List<Integer>> subanswer2 = insertAll(first, subanswer1);
		return concat(subanswer1, subanswer2);
	}

	private static List<List<Integer>> concat(List<List<Integer>> sub1, List<List<Integer>> sub2) {
		List<List<Integer>> list = new ArrayList<>();
		list.addAll(sub1);
		list.addAll(sub2);
		return list;
	}

	private static List<List<Integer>> insertAll(Integer first, List<List<Integer>> subanswer) {
		List<List<Integer>> list = new ArrayList<>();
		for (List<Integer> subSet : subanswer) {
			List<Integer> copyList = new ArrayList<>();
			copyList.add(first);
			copyList.addAll(subSet);
			list.add(copyList);
		}
		return list;
	}
}
